/*
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。

 

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

 

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2：

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
输出：[3.75000,0.40000,5.00000,0.20000]
示例 3：

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]
 

提示：

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj 由小写英文字母与数字组成
*/

#include "stdc++.h"

/* 广度优先搜索
我们可以将整个问题建模成一张图：给定图中的一些点（变量），以及某些边的权值（两个变量的比值），试对任意两点（两个变量）求出其路径长（两个变量的比值）。
因此，我们首先需要遍历 equations 数组，找出其中所有不同的字符串，并通过哈希表将每个不同的字符串映射成整数。
在构建完图之后，对于任何一个查询，就可以从起点出发，通过广度优先搜索的方式，不断更新起点与当前点之间的路径长度，直到搜索到终点为止。
*/
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int nVars{0}; 
        unordered_map<string, int> variables{}; // 通过哈希表将每个不同的字符串映射成整数

        for (const auto& equation : equations) {
            if (variables.find(equation[0]) == variables.end()) {
                variables[equation[0]] = nVars++;
            }
            if (variables.find(equation[1]) == variables.end()) {
                variables[equation[1]] = nVars++;
            }
        }

        int n = equations.size();
        // 对于每个点，存储其直接连接到的所有点及对应的权值
        vector<vector<pair<int, double>>> edges(nVars);
        for (int i{0}; i < n; ++i) {
            int va = variables[equations[i][0]];
            int vb = variables[equations[i][1]];
            edges[va].push_back(make_pair(vb, values[i]));
            edges[vb].push_back(make_pair(va, 1.0 / values[i]));
        }

        vector<double> ret{};
        for (const auto& q : queries) {
            double result{-1.0};
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int ia = variables[q[0]];
                int ib = variables[q[1]];
                if (ia == ib) { // 字符串相同
                    result = 1.0;
                } else {
                    queue<int> points{};
                    points.push(ia);
                    vector<double> ratios(nVars, -1.0);
                    ratios[ia] = 1.0;

                    while (!points.empty() && ratios[ib] < 0) { // ratios[ib] < 0 表示能算出结果，否则就是-1.0
                        int x = points.front();
                        points.pop();
                        for (const auto& p : edges[x]) {
                            int y = p.first;
                            double val = p.second;
                            if (ratios[y] < 0) {
                                ratios[y] = ratios[x] * val;
                                points.push(y);
                            }
                        }
                    }
                    result = ratios[ib];
                }
            }
            ret.push_back(result);
        }
        return ret;
    }
};

/* Floyd 算法
对于查询数量很多的情形，如果为每次查询都独立搜索一次，则效率会变低。为此，我们不妨对图先做一定的预处理，随后就可以在较短的时间内回答每个查询。
在本题中，我们可以使用 Floyd 算法，预先计算出任意两点之间的距离。
*/
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int nVars{0};
        unordered_map<string, int> variables{}; // 通过哈希表将每个不同的字符串映射成整数

        for (const auto& equation : equations) {
            if (variables.find(equation[0]) == variables.end()) {
                variables[equation[0]] = nVars++;
            }
            if (variables.find(equation[1]) == variables.end()) {
                variables[equation[1]] = nVars++;
            }
        }

        int n = equations.size();
        vector<vector<double>> graph(nVars, vector<double>(nVars, -1.0));
        for (int i{0}; i < n; ++i) {
            int va = variables[equations[i][0]];
            int vb = variables[equations[i][1]];
            graph[va][vb] = values[i];
            graph[vb][va] = 1.0 / values[i];
        }

        // 对图进行预处理
        for (int k{0}; k < nVars; ++k) {
            for (int i{0}; i < nVars; ++i) {
                for (int j{0}; j < nVars; ++j) {
                    if (graph[i][k] > 0 && graph[k][j] > 0) {
                        graph[i][j] = graph[i][k] * graph[k][j];
                    }
                }
            }
        }

        vector<double> ret{};
        for (const auto& q : queries) {
            double result{-1.0};
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int ia = variables[q[0]];
                int ib = variables[q[1]];
                if (graph[ia][ib] > 0) {
                    result = graph[ia][ib];
                }
            }
            ret.push_back(result);
        }
        return ret;
    }
};

/* 带权并查集
以并查集的方式存储节点之间的关系。设节点 x 的值（即对应变量的取值）为 v[x]。对于任意两点 x,y，假设它们在并查集中具有共同的父亲 f，且 v[x]/v[f] = a, v[y]/v[f]=b，则 v[x]/v[y]=a/b。
在观察到这一点后，就不难利用并查集的思想解决此题。对于每个节点 x 而言，除了维护其父亲 f[x] 之外，还要维护其权值 w，其中「权值」定义为节点 x 的取值与父亲 f[x] 的取值之间的比值。

*/
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int nVars{0};
        unordered_map<string, int> variables{}; // 通过哈希表将每个不同的字符串映射成整数

        for (const auto& equation : equations) {
            if (variables.find(equation[0]) == variables.end()) {
                variables[equation[0]] = nVars++;
            }
            if (variables.find(equation[1]) == variables.end()) {
                variables[equation[1]] = nVars++;
            }
        }
        
        int n = equations.size();
        vector<int> f(nVars, 0);
        vector<double> w(nVars, 1.0);
        for (int i{0}; i < nVars; ++i) {
            f[i] = i;
        }

        for (int i{0}; i < n; ++i) {
            int va = variables[equations[i][0]];
            int vb = variables[equations[i][1]];
            merge(f, w, va, vb, values[i]);
        }

        vector<double> ret{};
        for (const auto& q : queries) {
            double result = -1.0;
            if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) {
                int ia = variables[q[0]];
                int ib = variables[q[1]];
                int fa = findf(f, w, ia);
                int fb = findf(f, w, ib);
                if (fa == fb) {
                    result = w[ia] / w[ib];
                }
            }
            ret.push_back(result);
        }
        return ret;
    }

    int findf(vector<int>& f, vector<double>& w, int x) {
        if (f[x] != x) {
            int father = findf(f, w, f[x]);
            w[x] = w[x] * w[f[x]];
            f[x] = father;
        }
        return f[x];
    }
    void merge(vector<int>& f, vector<double>& w, int x, int y, double val) {
        int fx = findf(f, w, x);
        int fy = findf(f, w, y);
        f[fx] = fy;
        w[fx] = val * w[y] / w[x];
    }
};